Functional monitoring problems are fundamental in distributed systems, in particular sensor networks, where minimization of communication is necessary. Functional monitoring also concerns problems in communication complexity, communication theory, and signal processing.
In traditional sensor systems such as smart homes and elsewhere, security sensors are carefully laid out and configured, and there is a convenient power source. The straightforward way to monitor a phenomenon is to take measurements every few time instants, send them to a central site, and use back-end systems to analyze the entire data trace.
In contrast, modern sensor networks, addressed in this invention, are more ad hoc and mobile. A modern sensor network may be distributed arbitrarily, operate on battery power, and have expensive bandwidth costs (e.g., via wireless communication). A battery operated device needs to conserve their power for long use between charging periods. Further, these sensors have some memory and computing power. Hence the sensors can perform local computations and be more careful in usage of radio for communication, since radio use is the biggest source of battery drain. In this scenario, collecting all the data from sensors to correctly calculate a function in the back-end is wasteful, and a direct approach is to design protocols which will trigger an alarm when a threshold is exceeded, and the emphasis is on minimizing the communication during the battery lifetime.
Moreover, even in a hard wired (i.e., not wireless) environment, there is a bandwidth cost to transmitting data, and minimization of communication of purely overhead functions is a generally desirable feature.
In this context, variations of functional monitoring have been proposed as “reactive monitoring” (in networking, see M. Dilman and D. Raz, “Efficient reactive monitoring,” IEEE Infocom, 2001), and “distributed triggers” (in databases, see G. Cormode and M. Garofalakis, “Sketching streams through the net: Distributed approximate query tracking,” Intl. Conf. Very Large Data Bases, 2005; G. Cormode, S. Muthukrishnan, and W. Zhuang, “What's different: Distributed, continuous monitoring of duplicate resilient aggregates on data streams,” Intl. Conf. on Data Engineering, 2006; and G. Comiode, S. Muthukrishnan, and W. Zhuang, “Conquering the divide: Continuous clustering of distributed data streams,” Intl. Conf. on Data Engineering, 2007).
Prior work has considered many different functions, and typically presents algorithms with correctness guarantees, but no nontrivial communication bounds. Some of the above work takes a distributed streaming approach where in addition to optimizing the bits communicated, the algorithms also attempt to optimize the space and time requirements of each of the sensors.